/*
 * File   : includes/nPatriciaTrie.h
 * Author : Nandakiran Kirubanandan
 *
 * This file contains inline definitions of the Patricia Trie functions.
 *
 */

#ifndef __npatriciatrie_h
#define __npatriciatrie_h
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include "linkedlist.h"

extern char *commonheadkey;

typedef char* nPatriciaTrieKey;
template <class T> class nPatriciaTrie;

/*!
 * nPatriciaTrieNode: A node in a PATRICIA trie.
 * -  Each node stores one key, and the data associated with that key.
 * -  left and right pointers to the children in the PATRICIA trie
 */    
template <class T>
class nPatriciaTrieNode {
	private:
		friend class nPatriciaTrie<T>;
		int bit_index;
		nPatriciaTrieKey        key;
		T                       data;
		nPatriciaTrieNode<T>*   left;
		nPatriciaTrieNode<T>*   right;
		
	public:

		// Constructors & destructor
		nPatriciaTrieNode();
		nPatriciaTrieNode(nPatriciaTrieKey, T, int, nPatriciaTrieNode<T>*, nPatriciaTrieNode<T>*);
		virtual ~nPatriciaTrieNode();

		// Name:    Initialize
		// Args:    key, data, Bit-index, left, right
		// Return:  void
		// Purpose: Initialize this node with the given data.
		void	Initialize(nPatriciaTrieKey, T, int, nPatriciaTrieNode<T>*, nPatriciaTrieNode<T>*);

		// Name:	GetData/SetData
		// Args:	data : T
		// Return:	T | bool
		// Purpose:	Accessors for the data field.
		T      GetData();
		bool   SetData(T);
		
		// Name:	GetKey
		// Args:	none
		// Return:	char*
		// Purpose:	Getter for the key field.
		nPatriciaTrieKey        GetKey();

		// Name:	GetLeft/GetRight
		// Args:	none
		// Return:	nPatriciaTrieNode*
		// Purpose:	Getters for the left/right fields.
		nPatriciaTrieNode<T>*   GetLeft();
		nPatriciaTrieNode<T>*   GetRight();

		void	DeleteKey();


};

/*! 
 * nPatriciaTrie: Implements a PATRICIA trie structure with keys of type
 *  - nPatriciaTrieKey (currently char*, but can be changed, see
 *    the definition of nPatriciaTrieKey above).
 */
template <class T>
class nPatriciaTrie {
	private:
		int  bit_get(nPatriciaTrieKey, int);
		int  bit_first_different(nPatriciaTrieKey, nPatriciaTrieKey);
		bool key_compare(nPatriciaTrieKey, nPatriciaTrieKey);
		void key_copy(nPatriciaTrieNode<T>*, nPatriciaTrieNode<T>*);
		long keyno;		
		nPatriciaTrieNode<T>* specialRoot;
		nPatriciaTrieKey lastproc; // Last processed key for getNitems		
		bool foundthenode; // used by searchThenListRest
		linkedlist keylist;
	public:
		nPatriciaTrieNode<T>* head;
		long triesize;		
		void recursive_remove(nPatriciaTrieNode<T>* &root);
		void recursive_remove_delete(nPatriciaTrieNode<T>* &root);

		// Constructor and destructor
		nPatriciaTrie();
		virtual ~nPatriciaTrie();

		// Name:	Insert(key, data)
		// Args:	key : nPatriciaTrieKey, data : T
		// Return:	nPatriciaTrieNode*
		// Purpose:	Insert a new key+data pair in the Patricia structure, and
		//          return the new node.
		virtual nPatriciaTrieNode<T>*   Insert(nPatriciaTrieKey, T);

		// Name:	Lookup(key)
		// Args:	key : nPatriciaTrieKey
		// Return:	T
		// Purpose:	Search for the given key, and return the data associated
		//          with it (or NULL).
		virtual T                       Lookup(nPatriciaTrieKey);

		// Name:	LookupNextNode(key)
		// Args:	key : nPatriciaTrieKey
		// Return:	T
		// Purpose:	Search for key just greater than the given
		// 		key and return the node that contains it (or NULL)
		virtual nPatriciaTrieNode<T>*   LookupNextNode(nPatriciaTrieKey);

		// Name:	LookupNode(key)
		// Args:	key : nPatriciaTrieKey
		// Return:	T
		// Purpose:	Search for the given key, and return the node that
		//          contains it (or NULL).
		virtual nPatriciaTrieNode<T>*   LookupNode(nPatriciaTrieKey);
		
		// Name:	Delete(key)
		// Args:	key : nPatriciaTrieKey
		// Return:	bool
		// Purpose:	Remove the node containing the given key. Return
	        //              true if the operation succeeded, false otherwise.
		virtual bool                    Delete(nPatriciaTrieKey);


		// Name:	isEmpty()
		// Args:	none
		// Return:	bool
		// Purpose:	To check whether the trie is empty or not
		virtual bool			isEmpty();
		
		// Name:	GetKey(N)
		// Args:	n : long  - to get the N'th key 
		// Return:	linkedlist*
		// Purpose:	Returns the a pointer to linked list containing 
		// 		the N'th key
		virtual linkedlist*		GetKey(long N);
		
		// Name:	GetRandomKey()
		// Args:	none
		// Return:	nPatriciaTrieKey
		// Purpose:	Returns a random key from the trie
		virtual nPatriciaTrieKey GetRandomKey();
		
		// Name:	getList()
		// Args:	none
		// Return:	linkedlist*
		// Purpose:	Returns the a pointer to linked list containing all 
		// 		the elements in the trie.
		virtual linkedlist*		getList();
		
		// Name:	recurseN(nPatriciaTrieNode*)
		// Args:	x : nPatriciaTrieNode* - the current node
		// Return:	None
		// Purpose:	Perform a recursive search from the node specified till N keys
		// 		are found.
		virtual void			recurseN(nPatriciaTrieNode<T>* x,int N);
		
		// Name:	recurse(nPatriciaTrieNode*)
		// Args:	x : nPatriciaTrieNode* - the current node
		// Return:	None
		// Purpose:	Perform a recursive search from the node specified and populate
		// 		a list containing the elements in the sub trie.
		virtual void			recurse(nPatriciaTrieNode<T>* x);

		// Name:	searchThenListRest(int,nPatriciaTrieNode<T>*,int)
		// Args: 	howManyItems : int : the Total no of items to list
		// 		count        : Starting count (generally zero)
		// 		nPatriciaTrieNode<T>* cur : current node 
		// Return:	None
		// Purpose:	Search for a node (specified by last proc), and then
		// 		list 'N' items after the node (N specified by howManyItems)
		virtual void			searchThenListRest(int howManyItems,
								   nPatriciaTrieNode<T> *cur,
								   int &count
								   );			
		// Name:	getPartialList(nPatriciaTrieKey)
		// Args:	k : nPatriciaTrieKey - Partial Key
		// Return:	linkedlist
		// Purpose:	Returns the a pointer to linked list containing all 
		// 		the elements in the trie that begin with the partial key.
		virtual linkedlist* 		getPartialList(nPatriciaTrieKey k);
		
		
		// Name:	getNitems(int,bool)
		// Args:	n      : int - How many
		// 		first  : bool - From begining?y
		// Return:	linkedlist
		// Purpose:	Returns the a pointer to linked list containing at most n items from 
		// 		the elements in the trie.
		virtual linkedlist* 		getNitems(int n,bool first);


		// Name:	specialRecurse(nPatriciaTrieNode*,nPatriciaKey)
		// Args:	x : nPatriciaTrieNode* - the current node
		// 		k : nPatriciaTrieKey   - the partial key
		// Return:	None
		// Purpose:	Perform a recursive search from the node specified and populate a list
		// 		containind the elements begining with the partial key, in the sub trie.
		virtual void			specialRecurse(nPatriciaTrieNode<T>* x,nPatriciaTrieKey k);
		
		
		bool saveToFile();
		virtual void  deleteMemory();
};

//----------------------------------------------------------------------------
template <class T>
nPatriciaTrieNode<T>::nPatriciaTrieNode() {
	Initialize(NULL, (T)NULL, -1, this, this);
}

//----------------------------------------------------------------------------
template <class T>
nPatriciaTrieNode<T>::nPatriciaTrieNode(nPatriciaTrieKey k,
                                        T d,
                                        int bi,
                                        nPatriciaTrieNode<T>* l,
                                        nPatriciaTrieNode<T>* r) {
    Initialize(k, d, bi, l, r);
}

//----------------------------------------------------------------------------
template <class T>
void nPatriciaTrieNode<T>::Initialize(nPatriciaTrieKey k,
                                      T d,
                                      int bi,
                                      nPatriciaTrieNode<T>* l,
                                      nPatriciaTrieNode<T>* r) {
	key = k;
	data      = d;
	left      = l;
	right     = r;
	bit_index = bi;
}

//----------------------------------------------------------------------------
template <class T>
void nPatriciaTrieNode<T>::DeleteKey() {
	free(key);
	key = NULL;
}

//----------------------------------------------------------------------------
template <class T>
nPatriciaTrieNode<T>::~nPatriciaTrieNode() {
	key = NULL;
}

//----------------------------------------------------------------------------
template <class T>
T nPatriciaTrieNode<T>::GetData() {
	return data;
}

//----------------------------------------------------------------------------
template <class T>
bool nPatriciaTrieNode<T>::SetData(T d) {
	memcpy(&data, &d, sizeof(T));
	return true;
}

//----------------------------------------------------------------------------
template <class T>
nPatriciaTrieKey nPatriciaTrieNode<T>::GetKey() {
	return key;
}

//----------------------------------------------------------------------------
template <class T>
nPatriciaTrieNode<T>* nPatriciaTrieNode<T>::GetLeft() {
	return left;
}

//----------------------------------------------------------------------------
template <class T>
nPatriciaTrieNode<T>* nPatriciaTrieNode<T>::GetRight() {
	return right;
}

//----------------------------------------------------------------------------
template <class T>
nPatriciaTrie<T>::nPatriciaTrie() {
	// Create the head of the structure. The head is never moved
	// around in the trie (i.e. it always stays at the top of the structure).
        // This prevents further complications having to do with node removal.
	head = new nPatriciaTrieNode<T>();
	if (commonheadkey==NULL) {
		#define ZEROTAB_SIZE 256
		commonheadkey = (char*)calloc(ZEROTAB_SIZE, 1);
	}
	head->key=commonheadkey;
	triesize=0;
	lastproc=NULL;
}

//----------------------------------------------------------------------------
template <class T>
void nPatriciaTrie<T>::deleteMemory() {
	recursive_remove_delete(head);
}
//----------------------------------------------------------------------------
template <class T>
nPatriciaTrie<T>::~nPatriciaTrie() {
	keylist.removeAll();
	if(lastproc!=NULL)
		free(lastproc);
	recursive_remove(head);
}

//----------------------------------------------------------------------------
template <class T>
nPatriciaTrieNode<T>* nPatriciaTrie<T>::Insert(nPatriciaTrieKey k, T d) {
	
	nPatriciaTrieNode<T> *p, *t, *x;
	// Start at the root
	p = head;
	t = (nPatriciaTrieNode<T>*)(p->right);

	// Navigate down the tree and look for the key
	while (p->bit_index < t->bit_index) {
		p = t;
		t = (nPatriciaTrieNode<T>*)(bit_get(k, t->bit_index) ? t->right : t->left);
	}

	// Is the key already in the tree?
	if (key_compare(k, t->key))
		return NULL; // Already in the tree!

	// Find the first bit that does not match.
	int i = bit_first_different(k, t->key);

	// Find the appropriate place in the tree where
	// the node has to be inserted
	p  = head;
	x  = (nPatriciaTrieNode<T>*)(p->right);
	while ( ( p->bit_index < x->bit_index ) &&
			( x->bit_index < i) ) {
		p = x;
		x = (nPatriciaTrieNode<T>*)(bit_get(k, x->bit_index) ? x->right : x->left);
	}


	// Allocate a new node and initialize it.
	t = new nPatriciaTrieNode<T>();
	if (t==NULL) {
		printf("Memory allocate Error!!\n");
		return NULL;
	}
	t->Initialize(k, d, i, (bit_get(k, i) ? x : t), (bit_get(k, i) ? t : x));
  	triesize++;	
	// Rewire
	if (bit_get(k, p->bit_index))
		p->right = t;
	else
		p->left = t;

	// Return the newly created node
	return t;

}

//----------------------------------------------------------------------------
template <class T>
void nPatriciaTrie<T>::recurseN(nPatriciaTrieNode<T>* x,int N) {
	// In Order Processing 
	nPatriciaTrieNode<T>* tmp;
	tmp = x->left;
	if ((x->bit_index<tmp->bit_index) && (x!=tmp) && (x!=head))
		// Child is a valid child
		recurseN(tmp,N);
	else if(tmp!=head) {
		keyno++;
		if (keyno>=N) {
			keylist.add(tmp->key);
			return;
		}
	}
	tmp = x->right;
	if ((x->bit_index<tmp->bit_index) && (x!=tmp) && (x!=head))
		// Child is a valid child
		recurseN(tmp,N);
	else if(tmp!=head) {
		keyno++;
		if (keyno>=N) {
			keylist.add(tmp->key);
			return;
		}
	}
}
//----------------------------------------------------------------------------
template <class T>
void nPatriciaTrie<T>::recurse(nPatriciaTrieNode<T>* x) {
	// In Order Processing 
	nPatriciaTrieNode<T>* tmp;
	tmp = x->left;
	if ((x->bit_index<tmp->bit_index) && (x!=tmp) && (x!=head))
		// Child is a valid child
		recurse(tmp);
	else if(tmp!=head)
		keylist.add(tmp->key);
	tmp = x->right;
	if ((x->bit_index<tmp->bit_index) && (x!=tmp) && (x!=head))
		// Child is a valid child
		recurse(tmp);
	else if(tmp!=head)
		keylist.add(tmp->key);

}
//----------------------------------------------------------------------------
template <class T>
void nPatriciaTrie<T>::searchThenListRest(int howManyItems,
				   	  nPatriciaTrieNode<T> *cur,
					  int &count
		) {
	bool skipleft=false;
	if (count>=howManyItems)
		return;
	if ((!foundthenode) 
	       	&& !(bit_get(lastproc,cur->bit_index))) {
			if (cur->bit_index < cur->left->bit_index) 
				searchThenListRest(howManyItems,cur->left,count);
			else
				if (strcmp(lastproc,cur->left->key)==0)
					foundthenode=true;
			skipleft=true;
	}

	if ((!foundthenode) 
	       	&& (bit_get(lastproc,cur->bit_index))) {
			if (cur->bit_index < cur->right->bit_index) 
				searchThenListRest(howManyItems,cur->right,count);
			else
				if (strcmp(lastproc,cur->right->key)==0)
					foundthenode=true;
			return;
	}

	if (foundthenode) {
		nPatriciaTrieNode<T>* tmp;
		if (!skipleft) {
			tmp = cur->left;
			if ((cur->bit_index<tmp->bit_index) && (cur!=tmp) && (cur!=head))
				// Child is a valid child
				searchThenListRest(howManyItems,tmp,count);
			else {
				if (count>=howManyItems)
					return;
				if (tmp!=head) {
					keylist.add(tmp->key);
					if (lastproc!=NULL)
						free(lastproc);
					lastproc=(nPatriciaTrieKey)strdup(tmp->key);
					count++;
				}
			}
                }
		if (count>=howManyItems)
			return;
		
		tmp = cur->right;
		if ((cur->bit_index<tmp->bit_index) && (cur!=tmp) && (cur!=head))
			// Child is a valid child
			searchThenListRest(howManyItems,tmp,count);
		else {
			if (count>=howManyItems)
				return;
			if (tmp!=head) {
				keylist.add(tmp->key);
				if (lastproc!=NULL)
					free(lastproc);
				lastproc=(nPatriciaTrieKey)strdup(tmp->key);
				count++;
			}
		}
	}	
}
	
//----------------------------------------------------------------------------
template <class T>
void nPatriciaTrie<T>::specialRecurse(nPatriciaTrieNode<T>* x,nPatriciaTrieKey k) {
	nPatriciaTrieNode<T>* tmp;
	if(!(beginsWith(x->key,k)))
		return;
	keylist.add(x->key);
	tmp = x->left;
	if ((tmp!=x) && (tmp!=head) && (tmp!=specialRoot)) {
		if ((x->bit_index<tmp->bit_index))
			// Child is a valid child
			specialRecurse(tmp,k);
		else
			if (beginsWith(tmp->key,k))
				keylist.add(tmp->key);	
	}
	tmp = x->right;
	if ((tmp!=x) && (tmp!=head) && (tmp!=specialRoot)) {
		if ((x->bit_index<tmp->bit_index))
			// Child is a valid child
			specialRecurse(tmp,k);
		else
			if(beginsWith(tmp->key,k))
				keylist.add(tmp->key);	
	}

}
//----------------------------------------------------------------------------
template <class T>
linkedlist* nPatriciaTrie<T>::GetKey(long N) {
	keylist.removeAll();	
	keyno=0;
	nPatriciaTrieNode<T>* x;
	// Start at the root.
	x = (nPatriciaTrieNode<T>*)(head->right);
	if (x!=head)
	  recurseN(x,N);
	return keylist.copyList();
}

//----------------------------------------------------------------------------
template <class T>
nPatriciaTrieKey  nPatriciaTrie<T>::GetRandomKey() {

	nPatriciaTrieNode<T> *p, *t;
	// Start at the root
	p = head;
	t = (nPatriciaTrieNode<T>*)(p->right);

	// Navigate down the tree and look for the key
	while (p->bit_index < t->bit_index) {
		p = t;
		t = (nPatriciaTrieNode<T>*)(rand()%2) ? t->right : t->left;
	}

	return strdup(t->key);
}

//----------------------------------------------------------------------------
template <class T>
linkedlist* nPatriciaTrie<T>::getList() {
        keylist.removeAll();	
	nPatriciaTrieNode<T>* x;
	// Start at the root.
	x = (nPatriciaTrieNode<T>*)(head->right);
	if (x!=head)
	  recurse(x);
	return keylist.copyList();
}

//----------------------------------------------------------------------------
template <class T>
bool nPatriciaTrie<T>::isEmpty() {
	nPatriciaTrieNode<T>* r = (nPatriciaTrieNode<T>*)head->right;
	nPatriciaTrieNode<T>* l = (nPatriciaTrieNode<T>*)head->left;
	if (l==r)
		return true;
	return false;
}
//----------------------------------------------------------------------------
template <class T>
T nPatriciaTrie<T>::Lookup(nPatriciaTrieKey k) {

	// Lookup the node
	nPatriciaTrieNode<T>* node = LookupNode(k);

	// Failed?
	if (!node)
		return (T)NULL;

	// Return the data stored in this node
	return node->data;

}
//----------------------------------------------------------------------------
template <class T>
nPatriciaTrieNode<T>* nPatriciaTrie<T>::LookupNextNode(nPatriciaTrieKey k) {
	bool alreadypresent;
	int count=0;
 	char* tmpkey;
	tmpkey=NULL;
	if (LookupNode(k)!=NULL) 
		alreadypresent=true;
	else {
		alreadypresent=false;
		tmpkey=strdup(k);
		Insert(tmpkey,(T)NULL);
	}
	
	foundthenode=false;
	if (lastproc!=NULL)
		free(lastproc);
	lastproc = (nPatriciaTrieKey)strdup(k);
	keylist.removeAll();
	
	searchThenListRest(1,head,count); 
	
	char *str;
	if (keylist.count()==1)
		str=strdup(keylist.remove());
	if (!alreadypresent) {
		Delete(k);
		free(tmpkey);
	}
	if (count==1)
		// Return the node
		return LookupNode(str);
	else
		return NULL;

}

//----------------------------------------------------------------------------
template <class T>
nPatriciaTrieNode<T>* nPatriciaTrie<T>::LookupNode(nPatriciaTrieKey k) {

	nPatriciaTrieNode<T>* p;
	nPatriciaTrieNode<T>* x;


	// Start at the root.
        p = head;
	x = (nPatriciaTrieNode<T>*)(head->right);

	// Go down the Patricia structure until an upward
	// link is encountered.
	while (p->bit_index < x->bit_index) {
		p = x;
		x = (nPatriciaTrieNode<T>*)(bit_get(k, x->bit_index) ? x->right : x->left);
	}

	// Perform a full string comparison, and return NULL if
	// the key is not found at this location in the structure.
	if (!key_compare(k, x->key))
		return NULL;

	// Return the node
	return x;

}

//----------------------------------------------------------------------------
template <class T>
bool nPatriciaTrie<T>::Delete(nPatriciaTrieKey k) {

	nPatriciaTrieNode<T> *p, *t, *x, *pp, *lp;
	int bp, bl, br;
	char* key = NULL;

	// Start at the root
	p  = head;
	t  = (nPatriciaTrieNode<T>*)(p->right);

	// Navigate down the tree and look for the key
	while (p->bit_index < t->bit_index) {
		pp = p;
		p  = t;
		t  = (nPatriciaTrieNode<T>*)(bit_get(k, t->bit_index) ? t->right : t->left);
	}

	// Is the key in the tree? If not, get out!
	if (!key_compare(k, t->key))
		return false; // The key could not be found!

	// Copy p's key to t
	if (t != p)
		key_copy(p, t);

	// Is p a leaf?
	bp = p->bit_index;
	bl = ((nPatriciaTrieNode<T>*)(p->left))->bit_index;
	br = ((nPatriciaTrieNode<T>*)(p->right))->bit_index;

	if ((bl > bp) || (br > bp)) {
		
        // There is at least one downward edge.

		if (p != t) {
			
			// Look for a new (intermediate) key
			key = strdup(p->key);

			lp = p;
			x  = (nPatriciaTrieNode<T>*)(bit_get(key, p->bit_index) ? p->right : p->left);
      
			while (lp->bit_index < x->bit_index) {
				lp = x;
				x  = (nPatriciaTrieNode<T>*)(bit_get(key, x->bit_index) ? x->right : x->left);
			}

			// If the intermediate key was not found, we have a problem..
			if (!key_compare(key, x->key)) {
				free(key);
				return false; // The key could not be found!
			}

			// Rewire the leaf (lp) to point to t
			if (bit_get(key, lp->bit_index))
				lp->right = t;
			else
				lp->left = t;

		}

		// Rewire the parent to point to the real child of p
		if (pp != p) {
			nPatriciaTrieNode<T>* ch = (nPatriciaTrieNode<T>*)(bit_get(k, p->bit_index) ? p->left : p->right);
			if (bit_get(k, pp->bit_index))
				pp->right = ch;
			else
				pp->left = ch;
		}

        // We no longer need 'key'
        free(key);
        key = NULL;
	
	} else {

		// Both edges (left, right) are pointing upwards or to the node (self-edges).
    
		// Rewire the parent
		if (pp != p) {
			nPatriciaTrieNode<T>* blx = (nPatriciaTrieNode<T>*)(p->left);
			nPatriciaTrieNode<T>* brx = (nPatriciaTrieNode<T>*)(p->right);
			if (bit_get(k, pp->bit_index))
				pp->right = (((blx == brx) && (blx == p)) ? pp : ((blx==p)?brx:blx));
			else
				pp->left  = (((blx == brx) && (blx == p)) ? pp : ((blx==p)?brx:blx));
		}

	}

	// Deallocate p (no longer needed)
	delete p;
	triesize--;	
	// Success!
	return true;

}

//----------------------------------------------------------------------------
template <class T>
void nPatriciaTrie<T>::recursive_remove_delete(nPatriciaTrieNode<T>* &root) {
	
	if (root==NULL)
		return;

	nPatriciaTrieNode<T>* l = (nPatriciaTrieNode<T>*)root->left;
	nPatriciaTrieNode<T>* r = (nPatriciaTrieNode<T>*)root->right;

	// Remove the left branch
	if ( (l->bit_index >= root->bit_index) && (l != root) && (l != head) )
		recursive_remove_delete(l);

	// Remove the right branch
	if ( (r->bit_index >= root->bit_index) && (r != root) && (r != head) )
		recursive_remove_delete(r);

	// Remove the root
	if (root!=head) {
		root->DeleteKey();
	}
	delete root;
	root=NULL;
}

//----------------------------------------------------------------------------
template <class T>
void nPatriciaTrie<T>::recursive_remove(nPatriciaTrieNode<T>* &root) {
	
	if (root==NULL)
		return;

	nPatriciaTrieNode<T>* l = (nPatriciaTrieNode<T>*)root->left;
	nPatriciaTrieNode<T>* r = (nPatriciaTrieNode<T>*)root->right;

	// Remove the left branch
	if ( (l->bit_index >= root->bit_index) && (l != root) && (l != head) )
		recursive_remove(l);

	// Remove the right branch
	if ( (r->bit_index >= root->bit_index) && (r != root) && (r != head) )
		recursive_remove(r);

	// Remove the root
	delete root;

}

//----------------------------------------------------------------------------
template <class T>
int nPatriciaTrie<T>::bit_get(nPatriciaTrieKey bit_stream, int n) {
  int len;
  len=strlen((char*)bit_stream);
  if ((len<<3)<=n)
	  return 0;
  if (n < 0 ) return 2; // "pseudo-bit" with a value of 2.
  int k = (n & 0x7);

  // ------------------------------------
  // Added by nandakiran kirubanandan
  // Added for in-order traversing to result in a sorted list 
  k = 7 - k;
  // ------------------------------------
  return ( (*(bit_stream + (n >> 3))) >> k) & 0x1;
}

//----------------------------------------------------------------------------
template <class T>
bool nPatriciaTrie<T>::key_compare(nPatriciaTrieKey k1, nPatriciaTrieKey k2) {
    if (!k1 || !k2)
        return false;
	return (strcmp((char*)k1, (char*)k2) == 0);
}

//----------------------------------------------------------------------------
template <class T>
int nPatriciaTrie<T>::bit_first_different(nPatriciaTrieKey k1, nPatriciaTrieKey k2) {
    if (!k1 || !k2)
        return 0; // First bit is different!
	int n = 0;
	int d = 0;
	while (	(k1[n] == k2[n]) &&
			(k1[n] != 0) &&
			(k2[n] != 0) )
		n++;
	while (bit_get(&k1[n], d) == bit_get(&k2[n], d))
		d++;
	return ((n << 3) + d);
}

//----------------------------------------------------------------------------
template <class T>
void nPatriciaTrie<T>::key_copy(nPatriciaTrieNode<T>* src, nPatriciaTrieNode<T>* dest) {

	if (src == dest)
		return;

	dest->key = src->key;
	
	/*
	// Copy the key from src to dest
	if (strlen(dest->key) < strlen(src->key))
		dest->key = (nPatriciaTrieKey)realloc(dest->key, 1 + strlen(src->key));
	strcpy(dest->key, src->key);
	*/

	// Copy the data from src to dest
	dest->data = src->data;
	
}
//----------------------------------------------------------------------------
template <class T>
linkedlist* nPatriciaTrie<T>::getNitems(int n,bool first) {
	int cnt=0;
	keylist.removeAll();
	foundthenode=false;
	if (first) {
		if (lastproc!=NULL)
			free(lastproc);
		lastproc=(nPatriciaTrieKey)strdup("");
		foundthenode=true;
	}
	//printf("%s %s %s\n",first?"True":"False",foundthenode?"Found":"Not Found",lastproc);
	searchThenListRest(n,head->right,cnt);
	return keylist.copyList();
}
//----------------------------------------------------------------------------
template <class T>
linkedlist* nPatriciaTrie<T>::getPartialList(nPatriciaTrieKey k) {
	nPatriciaTrieNode<T> *p, *t;

	// Start at the root
	p  = head;
	t  = (nPatriciaTrieNode<T>*)(p->right);
	 //printf("Key : %s (%d)\n",k,strlen(k)<<3);
	/// Navigate down the tree and look for the partial key
	while (p->bit_index < t->bit_index) {
		// printf("\t%s\t%d\t%d\n",t->key,t->bit_index,bit_get(k,t->bit_index));
		if(t->bit_index>(strlen(k)<<3))
			break;
		p=t;
		t  = (nPatriciaTrieNode<T>*)(bit_get(k, t->bit_index) ? t->right : t->left);
	}

	//printf("Key found : %s\n",t->key);
	if (!(beginsWith(p->key,k))) {
	  if (!(beginsWith(t->key,k))) {
		  return NULL;
	  } else { 
		specialRoot=t;
	  }
	} else {
		specialRoot=p;
	}

	keylist.removeAll();	
	specialRecurse(specialRoot,k);
	keylist.sort();
	keylist.removeDuplicates();
	return keylist.copyList();
}

//----------------------------------------------------------------------------
template <class T>
bool nPatriciaTrie<T>::saveToFile() {
        keylist.removeAll();	
	nPatriciaTrieNode<T>* x;
	// Start at the root.
	x = (nPatriciaTrieNode<T>*)(head->right);
	if (x!=head)
	  recurse(x);

	return keylist.saveToFile();
}

#endif

